package ca.etsmtl.log320.tp2;

import java.io.FileInputStream;
import java.io.IOException;

public class SudokuSolver 
{
	/* The number of cells in a sudoku grid */
	private static final int GRID_SIZE = 81;
	/* The number of possibilities for a single sudoku cell */
	private static final int CELL_SIZE = 9;
	/* ASCII code for "0" */
	private static final short ASCII_START = 48;
	/* ASCII code for "9" */
	private static final short ASCII_END = 57;
	/* Sum of a valid Sudoku */
	private static final int VALID = 405;
	/* No more empty cells */
	private static final int FILLED = -1;

	/* Sudoku possibilities */
	private static final short ONE = 16;
	private static final short TWO = 32;
	private static final short THREE = 64;
	private static final short FOUR = 128;
	private static final short FIVE = 256;
	private static final short SIX = 512;
	private static final short SEVEN = 1024;
	private static final short EIGHT = 2048;
	private static final short NINE = 4096;
	private static final short ALL = 8176;
	
	/* The Sudoku grid */
	private short[] grid = new short[GRID_SIZE];
	
	/* Total solving time */
	public long time;
	
	public SudokuSolver(String path)
	{		
		// Read the file
		read(path);
		
		// Print the original grid
		print(true);
	
		// Start the timer
		time = System.nanoTime();
		
		// Remove all obvious possibilities based on the original grid
		for(int i = 0; i < GRID_SIZE; i++)
		{
			// Make sure we're removing possibilities based on a filled cell
			if(grid[i] <= 9)
			{
				removePossibility(i, (short) (1 << grid[i] + 3));
			}
		}
		
		// Fill cells, lines and columns while removing possibilities
		while(fillCells() || fillLinesAndColumns());
		
		/* Intermediate solution */
		//print(true);
		
		// If the grid is valid and completed, don't even bother with the backtracking
		if(getGridSum() < VALID)
		{
			// If grid is not filled, brute force the puzzle
			solve(0);
		}
		
		// Stop the timer
		time = System.nanoTime() - time;
		
		// Final grid
		print(false);
	}
	
	/**
	 * Prints the grid in the console.
	 * @param printIncompleteGrid Make sure to pass true to this function if the grid is incomplete
	 * This will remove the bitmask used for possibilities
	 */
	private void print(boolean printIncompleteGrid)
	{
		/* Print the grid */
		String currentLine = "";
		for(int i = 0; i < GRID_SIZE; i += CELL_SIZE)
		{
			for(int j = 0; j < 9; j+=3)
			{
				if(printIncompleteGrid)
				{
					currentLine += (grid[i + j] & 15) + " " + (grid[i + j + 1] & 15) + " " + (grid[i + j + 2] & 15) + " | "; 
				}
				else
				{
					currentLine += grid[i + j] + " " + grid[i + j + 1] + " " + grid[i + j + 2] + " | "; 
				}
			}
			if (i % 27 == 0)
			{
				System.out.println("|-----------------------|");
			}
			System.out.println("| " + currentLine.substring(0, currentLine.length() - 3) + " |");
			currentLine = "";
		}
		System.out.println("|-----------------------|");
	}
	
	/**
	 * Reads the sudoku file byte by byte into the grid.
	 * All empty cells will initially have their possibilities mask
	 * set to "ALL"
	 * @param path The path to the sudoku file
	 */
	private void read(String path)
	{
		try
		{	
			FileInputStream in = new FileInputStream(path);
            int b;
            int position = 0;
            
            // Get all bytes from the file
            while ((b = in.read()) != -1)
			{ 
				// Ignore new lines and carriage returns
				if(b >= ASCII_START && b <= ASCII_END)
				{
					Short value = (short) (b - ASCII_START);
					
					/* If the cell is empty, set the possibility mask to all possibilities */
					if(value == 0)
					{
						grid[position] = ALL;
					}
					else
					{
						grid[position] = value;
					}
					
					position++;
				}
			}
			in.close();	
        }
		catch (IOException e)
		{
			e.printStackTrace();
		}
	}
	
	/**
	 * Remove the possibility given by "value" at a specific position.
	 * The corresponding column, line and square will also be affected.
	 * @param position The position to work on
	 * @param value The possibility to remove
	 */
	private void removePossibility(int position, short value)
	{
		/* Remove possibilities for all empty cells in the column, line and square */
		int column = position % CELL_SIZE;
		int line = position / CELL_SIZE;
		int square = (((position / 9) / 3) * 27) + ((column / 3) * 3);
		
		for(int j = 0; j < CELL_SIZE; j++)
		{
			/* Remove possibilities for line */
			if((grid[line * CELL_SIZE + j] & value) != 0) grid[line * CELL_SIZE + j] = (short) (grid[line * CELL_SIZE + j] ^ value);
			/* Remove possibilities for column */
			if((grid[j * CELL_SIZE + column] & value) != 0) grid[j * CELL_SIZE + column] = (short) (grid[j * CELL_SIZE + column] ^ value);
		}
		
		/* Remove possibilities for square */
		if((grid[square] & value) != 0) grid[square] = (short) (grid[square] ^ value);
		if((grid[square + 1] & value) != 0) grid[square + 1] = (short) (grid[square + 1] ^ value);
		if((grid[square + 2] & value) != 0) grid[square + 2] = (short) (grid[square + 2] ^ value);
		if((grid[square + 9] & value) != 0) grid[square + 9] = (short) (grid[square + 9] ^ value);
		if((grid[square + 10] & value) != 0) grid[square + 10] = (short) (grid[square + 10] ^ value);
		if((grid[square + 11] & value) != 0) grid[square + 11] = (short) (grid[square + 11] ^ value);
		if((grid[square + 18] & value) != 0) grid[square + 18] = (short) (grid[square + 18] ^ value);
		if((grid[square + 19] & value) != 0) grid[square + 19] = (short) (grid[square + 19] ^ value);
		if((grid[square + 20] & value) != 0) grid[square + 20] = (short) (grid[square + 20] ^ value);
	}
	
	/**
	 * Get the sum of all elements in the grid.
	 * A sum of 405 means the Sudoku is complete and valid.
	 * @return
	 */
	private int getGridSum()
	{
		int sum = 0;
		
		// Sum all cells in the grid
		for(int i = 0; i < GRID_SIZE; i++)
		{
			grid[i] = (short) (grid[i] & 15);
			sum += grid[i];
		}
		
		return sum;
	}
	
	/**
	 * Checks if a value is valid at a certain position in the grid
	 * @param position The position to check
	 * @param value The value to check
	 * @return true if the move is valid; Otherwise it will return false
	 */
	private boolean isValid(int position, short value)
	{	
		int division = position / 9;
		int lineCase =  division * 9;
		int columnCase = position % 9;
		int regionCase = ((division / 3) * 27) + ((columnCase / 3) * 3);
				
		for (int index = 0; index < 9; index++)
		{
			/* Check line */
			/* Don't check your own position */
			if (position != lineCase && grid[lineCase] == value)
				return false;
			lineCase++;
			
			/* Check column */
			/* Don't check your own position */
			if (position != columnCase && grid[columnCase] == value)
				return false;
			columnCase += 9;
			
			// Check region
			if (index < 3)
			{
				// Don't check your own position
				if (position != regionCase && grid[regionCase] == value)
					return false;
				// Don't check your own position
				if (position != (regionCase + 9) && grid[regionCase + 9] == value)
					return false;
				// Don't check your own position
				if (position != (regionCase + 18) && grid[regionCase + 18] == value)
					return false;
				regionCase++;
			}
		}
		return true;
	}
	
	/**
	 * Get the next empty cell for backtracking.
	 * Take note that the possibility mask should have been removed by now from
	 * all cells.
	 * @param position
	 * @return The position of the next empty cell
	 */
	private int getNextEmptyCell(int position)
	{
		for(; position < GRID_SIZE; position++)
		{
			if(grid[position] == 0)
			{
				return position;
			}
		}
		
		return FILLED;
	}
	
	/**
	 * Fill cells that have only one possibility with the correct value.
	 * @return true if at least one cell was changed; Otherwise it will return false
	 */
	private boolean fillCells()
	{
		boolean possibilitiesChanged = false; 
		
		/* Check every cell */
		for(int i = 0; i < GRID_SIZE; i++)
		{
			/* Only change cells with one possibility */
			switch(grid[i])
			{
				case ONE:
					grid[i] = 1;
					removePossibility(i, ONE);
					possibilitiesChanged = true;
					break;
					
				case TWO:
					grid[i] = 2;
					removePossibility(i, TWO);
					possibilitiesChanged = true;
					break;
					
				case THREE:
					grid[i] = 3;
					removePossibility(i, THREE);
					possibilitiesChanged = true;
					break;
					
				case FOUR:
					grid[i] = 4;
					removePossibility(i, FOUR);
					possibilitiesChanged = true;
					break;
					
				case FIVE:
					grid[i] = 5;
					removePossibility(i, FIVE);
					possibilitiesChanged = true;
					break;
					
				case SIX:
					grid[i] = 6;
					removePossibility(i, SIX);
					possibilitiesChanged = true;
					break;
					
				case SEVEN:
					grid[i] = 7;
					removePossibility(i, SEVEN);
					possibilitiesChanged = true;
					break;
					
				case EIGHT:
					grid[i] = 8;
					removePossibility(i, EIGHT);
					possibilitiesChanged = true;
					break;
					
				case NINE:
					grid[i] = 9;
					removePossibility(i, NINE);
					possibilitiesChanged = true;
					break;
			}
		}
		
		return possibilitiesChanged;
	}
	
	/**
	 * Fill lines and columns that can only accept one value
	 * @return true if at least one cell was changed; Otherwise it will return false
	 */
	private boolean fillLinesAndColumns()
	{		
		boolean possibilitiesChanged = false;
		
		/* Check all lines and columns */
		for(int lc = 0; lc < CELL_SIZE; lc++)
		{			
			/* Try all possible values */
			for(int value = 1; value <= CELL_SIZE; value++)
			{
				int line = -1;
				int column = -1;
				boolean unsolveableLine = false;
				boolean unsolveableColumn = false;
				
				/* Check all cells in a line and/or column */
				for(int offset = 0; offset < CELL_SIZE; offset++)
				{
					if((grid[lc * CELL_SIZE + offset] & (short) (1 << value + 3)) > 0 && !unsolveableLine)
					{
						if(line != -1)
						{
							unsolveableLine = true;
						}
						else
						{
							line = lc * CELL_SIZE + offset;
						}
					}
					
					if((grid[offset * CELL_SIZE + lc] & (short) (1 << value + 3)) > 0 && !unsolveableColumn)
					{
						if(column != -1)
						{
							unsolveableColumn = true;
						}
						else
						{
							column = offset * CELL_SIZE + lc;
						}
					}
				}
				
				if(!unsolveableLine && line >= 0) 
				{
					grid[line] = (short) value;
					removePossibility(line, (short) (1 << value + 3));
					possibilitiesChanged = true;
				}
				
				if(!unsolveableColumn && column >= 0)
				{
					grid[column] = (short) value;
					removePossibility(column, (short) (1 << value + 3));
					possibilitiesChanged = true;
				}
			}
		}
		
		return possibilitiesChanged;
	}
	
	/**
	 * Solve the sudoku with a backtracking algorithm
	 * @param position The position to start checking at
	 * @return true if the sudoku is solved; false if it's invalid
	 */
	private boolean solve(int position)
	{		
		/* Get the next empty cell */
		position = getNextEmptyCell(position);
		
		/* If the grid is filled, we can assume the Sudoku is solved */
		if(position == FILLED)
		{	
			return true;
		}
				
		/* Try brute forcing all possible values in the given cell */
		for(short i = 1; i <= 9; i++)
		{	
			// Is the move valid?
			if(isValid(position, i))
			{			
				grid[position] = i;
				
				// Keep solving until grid is filled
				if(solve(position + 1))
				{
					return true;
				}
			}
		}
		/* ... Or backtrack if no more moves are available! */
		grid[position] = (short) ((grid[position] >> 4) << 4);
		return false;
	}
}
